{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法简介\n",
    "    插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，其核心就在于插值的计算公式 (key-a[low])/(a[high]-a[low])*(high-low)。\n",
    "    时间复杂度o(logn)但对于表长较大而关键字分布比较均匀的查找表来说，效率较高。\n",
    "\n",
    "### 算法思想   \n",
    "    基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。\n",
    "    注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。\n",
    "\n",
    "### 复杂度分析 \n",
    "\n",
    "    时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要 O（n）。\n",
    "    空间复杂度：O（1）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "改进的二分查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(nums, key):\n",
    "    low = 0\n",
    "    high = len(nums) -1\n",
    "    \n",
    "    while low < high:\n",
    "        mid = low + int((key - nums[low]) * (high - low) / (nums[high] - nums[low]))\n",
    "        print(\"mid=%s, low=%s, high=%s\" % (mid, low, high))\n",
    "        \n",
    "        if key < nums[mid]:\n",
    "            high = mid -1\n",
    "        elif key > nums[mid]:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            return mid\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mid=2, low=0, high=10\n",
      "mid=4, low=3, high=10\n",
      "mid=5, low=5, high=10\n",
      "mid=6, low=6, high=10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]\n",
    "binary_search(nums, 99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
